988F - Rain and Umbrellas - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
#define int long long

const long long INF = 1e17 + 420 + 69;
signed main() {

    int a, n, m;
    cin >> a >> n >> m;

    vector<bool> israin(a + 1, 0);
 
    vector<int> is_left_end(a + 1, 0);
    for (int i = 0; i < n; i++) {

        int l, r;
        cin >> l >> r;
        is_left_end[l] = 1;

        for (int j = l; j <= r; j++) { //changed this 

            israin[j] = true;
        }
    }

    vector<int> up(a + 1, INF);
    vector<array<int, 2>> umb(1, {0, 0});

    for (int i = 0; i < m; i++) {

        int idx, p;
        cin >> idx >> p;

        up[idx] = min(up[idx], p);
    }

    for (int i = 0; i <= a; i++) {

        if (up[i] >= INF) {

            continue;
        }

        umb.push_back({i, up[i]});
    }

    m = umb.size();

    vector<vector<int>> dp(a + 1, vector<int> (m, INF));

    if (!israin[0]) {

        dp[0][0] = 0;
    }

    if (umb[1][0] == 0) {

        dp[0][1] = 0;
    }
    long long mn[a + 1][2];
    mn[0][0] = min(dp[0][0], dp[1][0]);
    mn[0][1] = dp[0][1] + umb[1][1];
    for (int i = 1; i <= a; i++) {

        if (!israin[i]) {

            for (int j = 0; j < m; j++) {

                dp[i][0] = min(dp[i][0], dp[i - 1][j]);
            }
        }

        for (int j = 1; j < m; j++) {

            if (umb[j][0] < i) {

                dp[i][j] = min(dp[i][j], dp[i - 1][j] + umb[j][1]);
            }

            else if (umb[j][0] == i) {

                if(!israin[i])
                    dp[i][j] = min(dp[i][j], dp[i][0]);
                else{
                    if(is_left_end[i]){
                        // dp[i][j] = min(dp[i][j], mn[i - 1][0]);
                        for(int k = 0; k < m; ++k){
                            dp[i][j] = min(dp[i][j], dp[i - 1][k]);
                        }
                        // dp[i][j] = min(dp[i][j], dp[i - 1][k] + umb[k][1] * (1 - is_left_end[i]));
                    }else{
                        // dp[i][j] = min(dp[i][j], mn[i - 1][1]);
                        for(int k = 1; k < m; ++k){
                            dp[i][j] = min(dp[i][j], dp[i - 1][k] + umb[k][1]);
                        }
                    }
                }
            }
            // mn[i][0] = mn[i][1] = INF;
            // for(int j = 0; j < m; ++j){
            //     mn[i][0] = min(mn[i][0], dp[i][j]);
            // }
            // for(int j = 1; j < m; ++j){
            //     mn[i][1] = min(mn[i][1], dp[i][j] + umb[j][1]);
            // }
        }
    }

    // for (int i = 0; i <= a; i++) {

    //     for (int j = 0; j < m; j++) {

    //         cerr << dp[i][j] << ' ';
    //     }
    //     cerr << "\n";
    // }

    long long ans = INF;
    for(int j = 0; j < m; ++j){
        ans = min(ans, (long long)dp[a][j]);
    }
    cout << (ans >= INF ? -1 : ans) << '\n';
}